lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/grafos/kruskal.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4
   5 using namespace std;
   6
   7 /*
   8 Algoritmo de Kruskal, para encontrar el árbol de recubrimiento de mínima suma.
   9 */
  10
  11 struct edge{
  12   int start, end, weight;
  13   bool operator < (const edge &that) const {
  14     //Si se desea encontrar el árbol de recubrimiento de máxima suma, cambiar el < por un >
  15     return weight < that.weight;
  16   }
  17 };
  18
  19
  20 /* Union find */
  21 int p[10001], rank[10001];
  22 void make_set(int x){ p[x] = x, rank[x] = 0; }
  23 void link(int x, int y){ rank[x] > rank[y] ? p[y] = x : p[x] = y, rank[x] == rank[y] ? rank[y]++: 0; }
  24 int find_set(int x){ return x != p[x] ? p[x] = find_set(p[x]) : p[x]; }
  25 void merge(int x, int y){ link(find_set(x), find_set(y)); }
  26 /* End union find */
  27
  28
  29 int main(){
  30   int c;
  31   cin >> c;
  32   while (c--){
  33     int n, m;
  34     cin >> n >> m;
  35     vector<edge> e;
  36     long long total = 0;
  37     while (m--){
  38       edge t;
  39       cin >> t.start >> t.end >> t.weight;
  40       e.push_back(t);
  41       total += t.weight;
  42     }
  43     sort(e.begin(), e.end());
  44     for (int i=0; i<=n; ++i){
  45       make_set(i);
  46     }
  47     for (int i=0; i<e.size(); ++i){
  48       int u = e[i].start, v = e[i].end, w = e[i].weight;
  49       if (find_set(u) != find_set(v)){
  50         //printf("Joining %d with %d using weight %d\n", u, v, w);
  51         total -= w;
  52         merge(u, v);
  53       }
  54     }
  55     cout << total << endl;
  56
  57   }
  58   return 0;
  59 }